import math
from collections import Counter
def euclidean_distance(x1, x2):
    return math.sqrt(sum((a - b) **2 for a, b in zip(x1, x2))
def knn_predict(X_train, y_train, x_test, k=3):
  
    if len(X_train) != len(y_train):
        raise ValueError("训练特征与标签数量不匹配")
    if k <= 0 or k > len(X_train):
        raise ValueError("k必须为正数且不大于训练样本数")
    
    distances = []
    for i, x_train in enumerate(X_train):
        dist = euclidean_distance(x_train, x_test)
        distances.append((dist, y_train[i])) 
    
    distances.sort()
    k_neighbors = distances[:k]
    
    k_labels = [label for (dist, label) in k_neighbors]
    most_common = Counter(k_labels).most_common(1) 
    return most_common[0][0]


def knn_classify(X_train, y_train, X_test, k=3):
    
    predictions = []
    for x_test in X_test:
        pred = knn_predict(X_train, y_train, x_test, k)
        predictions.append(pred)
    return predictions